从无监督构建词库看「最小熵原理」，套路是如何炼成的
作者丨苏剑林
单位丨广州火焰信息科技有限公司
研究方向丨NLP，神经网络
个人主页丨kexue.fm
在深度学习等端到端方案已经逐步席卷 NLP 的今天，你是否还愿意去思考自然语言背后的基本原理？我们常说“文本挖掘”，你真的感受到了“挖掘”的味道了吗？
无意中的邂逅
前段时间看了一篇关于无监督句法分析的文章 [1]，继而从它的参考文献中发现了论文 Redundancy Reduction as a Strategy for Unsupervised Learning，这篇论文介绍了如何从去掉空格的英文文章中将英文单词复原。对应到中文，这不就是词库构建吗？于是饶有兴致地细读了一番，发现论文思路清晰、理论完整、结果漂亮，让人赏心悦目。
尽管现在看来，这篇论文的价值不是很大，甚至其结果可能已经被很多人学习过了，但是要注意：这是一篇 1993 年的论文。在 PC 机还没有流行的年代，就做出了如此前瞻性的研究。
虽然如今深度学习流行，NLP 任务越做越复杂，这确实是一大进步，但是我们对 NLP 原理的真正了解，还不一定超过几十年前的前辈们多少。
这篇论文是通过“去冗余”（Redundancy Reduction）来实现无监督地构建词库的，从信息论的角度来看，“去冗余”就是信息熵的最小化。无监督句法分析那篇文章也指出“信息熵最小化是无监督的 NLP 的唯一可行的方案”。
我进而学习了一些相关资料，并且结合自己的理解思考了一番，发现这个评论确实是耐人寻味。我觉得，不仅仅是 NLP，信息熵最小化很可能是所有无监督学习的根本。
何为最小熵原理？
读者或许已经听说过最大熵原理和最大熵模型，现在这个最小熵原理又是什么？它跟最大熵不矛盾吗？
我们知道，熵是不确定性的度量，最大熵原理的意思就是说我们在对结果进行推测时，要承认我们的无知，所以要最大化不确定性，以得到最客观的结果。而对于最小熵原理，我们有两个理解角度：
1. 直观的理解：文明的演化过程总是一个探索和发现的过程，经过我们的努力，越多越多的东西从不确定变成了确定，熵逐渐地趋于最小化。因此，要从一堆原始数据中发现隐含的规律（把文明重演出来），就要在这个规律是否有助于降低总体的信息熵，因为这代表了文明演化的方向，这就是“最小熵原理”。
2. 稍严谨的理解：“知识”有一个固有信息熵，代表它的本质信息量。但在我们彻底理解它之前，总会有未知的因素，这使得我们在表达它的时候带有冗余，所以按照我们当前的理解去估算信息熵，得到的事实上是固有信息熵的上界，而信息熵最小化意味着我们要想办法降低这个上界，也就意味着减少了未知，逼近固有信息熵。
于是，我沿着“最小熵原理”这条路，重新整理了前人的工作，并做了一些新的拓展，最终就有了这些文字。读者将会慢慢看到，最小熵原理能用一种极具解释性和启发性的方法来导出丰富的结果来。
语言的信息
让我们从考究语言的信息熵开始，慢慢进入这个最小熵原理的世界。
信息熵=学习成本
从“熵”不起：从熵、最大熵原理到最大熵模型（一）[2] 我们可以知道，一个对象的信息熵是正比于它的概率的负对数的，也就是：
如果认为中文的基本单位是字，那么中文就是字的组合，pc 就意味着对应字的概率，而 −logpc 就是该字的信息量。我们可以通过大量的语料估算每个汉字的平均信息：
如果 log 是以 2 为底的话，那么根据网上流传的数据，这个值约是 9.65 比特（我自己统计了一些文章，得到的数值约为 9.5，两者相当）。类似地，英文中每个字母的平均信息约是 4.03 比特。
这个数字意味着什么呢？一般可以认为，我们接收或记忆信息的速度是固定的，那么这个信息量的大小事实上也就相当于我们接收这个信息所需要的时间（或者所花费的精力，等等），从而也可以说这个数字意味着我们学习这个东西的难度（记忆负荷）。比如，假设我们每秒只能接收 1 比特的信息，那么按字来记忆一篇 800 字文章，就需要 9.65×800 秒的时间。
中英文孰优孰劣？
既然中文单字信息熵是 9.65，而英文字母信息熵才 4.03，这是不是意味着英文是一种更高效的表达呢？
显然不能这么武断，难道背英语作文一定比背诵汉语作文要容易么？
比如 800 字的中文作文翻译成英文的话，也许就有 500 词了，平均每个英文 4 个字母，那么信息量就是 4.03×500×4≈9.65×800，可见它们是相当的。换句话说，比较不同文字单元的信息量是没有意义的，有意义的是信息总量，也就是说描述同样的意思时谁更简练。
当两句话的意思一样时，这个“意思”的固有信息量是不变的，但用不同语言表达时，就不可避免引入“冗余”，所以不同语言表达起来的信息量不一样，这个信息量其实就相当于记忆负荷，越累赘的语言信息量越大，记忆负荷越大。
就好比教同样的课程，有的老师教得清晰明了，学生轻松地懂了，有的老师教得哆里哆嗦，学生也学得很痛苦。同样是一节课程，本质上它们的知识量是一样的，而教得差的老师，表明授课过程中带来了过多的无关信息量，这就是“冗余”，所以我们要想办法“去冗余”。
上述中英文的估计结果相当，表明中英文都经过长期的优化，双方都大致达到了一个比较优化的状态，并没有谁明显优于谁的说法。
套路之路
注意，上面的估算中，我们强调了“按字来记忆”，也许我们太熟悉中文了，没意识到这意味着什么，事实上这代表了一种很机械的记忆方式，而我们事实上不是这样做的。
念经也有学问
回顾我们小时候背诵古诗、文言文的情景，刚开始我们是完全不理解、囫囵吞枣地背诵，也就是每个字都认识、串起来就不知道什么含义的那种，这就是所谓的“按字来阅读”了。很显然，这样的记忆难度是很大的。
后来，我们也慢慢去揣摩古文的成文规律了，逐渐能理解一些古诗或文言文的含义了，背诵难度就会降下来。到了高中，我们还会学习到文言文中“宾语前置”、“定语后置”之类的语法规律，这对我们记忆和理解文言文都是很有帮助的。
重点来了！
从古文的例子我们就能够感受到，像念经一样逐字背诵是很困难的，组词理解后就容易些，如果能找到一些语法规律，就更加容易记忆和理解了。但是我们接收（记忆）信息的速度还是固定的，这也就意味着分词、语法这些步骤，降低了语言的信息量，从而降低了我们的学习成本。
再细想一下，其实不单单是语言，我们学习任何东西都是这样的，如果只有少数的内容要学习，那么我们强行记住就行了，但学习的东西比较多时，我们就试图找出其中的“套路”，比如中国象棋中就分开局、中局、残局，每种局面都有很多“定式”，用来降低初学者的学习难度，而且也是在复杂局面中应变的基础；再好比我们有《孙子兵法》、《三十六计》，这些都是“套路大全”。通过挖掘“套路”来减轻逐一记忆的负担，“套路”的出现就是一个减少信息量的过程。
说到底，念经念多了，也能发现经文的套路了。
以不变应万变
一言以蔽之，我们接收信息的速度是固定的，所以加快我们的学习进度的唯一方法就是降低学习目标的冗余信息量，所谓“去芜存菁”，这就是 NLP 中的最小熵原理了，也就是一开始所提到的“去冗余”，我们可以理解为是“省去没必要的学习成本”。
事实上，一个高效的学习过程必定能体现出这个思想，同样地，教师也是根据这个思想来设计他们的教学计划的。在教学的时候，教师更倾向于讲授那些“通解通法”（哪怕步骤多一点），也不会选择每一题都讲一种独特的、巧妙的解法；在准备高考时，我们会努力摸索各种出题套路、解题套路。这些都是通过挖掘“套路”来降低信息熵、从而降低学习成本的过程，“套路”就是“去冗余”的方法。
“套路”即“定式”，有了足够多的套路，我们才能以不变应万变。所谓“万变不离其宗”，这个“宗”，也就是套路了吧。当“套路”过多时，我们又会进一步寻找“套套路”——即套路的套路，来减轻我们记忆套路的负担，这是一个层层递进的过程。看来，将个体现象上升为套路，正是人类的智能的体现呢。
好了，空话不宜多说，接下来我们就正式走上修炼套路的旅途。
这部分，我们介绍“套路宝典”第一式——“当机立断”：
1. 导出平均字信息熵的概念，然后基于最小熵原理推导出互信息公式；
2. 并且完成词库的无监督构建、给出一元分词模型的信息熵诠释，从而展示有关生成套路、识别套路的基本方法和技巧。这既是最小熵原理的第一个使用案例，也是整个“套路宝典”的总纲。
由字到词
从上文可以看到，假设我们根本不懂中文，那么我们一开始会将中文看成是一系列“字”随机组合的字符串，但是慢慢地我们会发现上下文是有联系的，它并不是“字”的随机组合，它应该是“套路”的随机组合。于是为了减轻我们的记忆成本，我们会去挖掘一些语言的“套路”。第一个“套路”，是相邻的字之间的组合定式，这些组合定式，也就是我们理解的“词”。
平均字信息熵
假如有一批语料，我们将它分好词，以词作为中文的单位，那么每个词的信息量是 −logpw，因此我们就可以计算记忆这批语料所要花费的时间为：
这里 w∈语料是对语料逐词求和，不用去重。如果不分词，按照字来理解，那么需要的时间为：
根据前一节的理解，分词其实就是为了减轻记忆负担，那么理论上应该有：
当然，很多词语是重复出现的，因此我们可以把相同项合并：
其中 Nw，Nc 分别是在语料中统计得到词和字的频数。对式 (2.4) 两边除以语料的总字数，那么右端就是：
其中 Nc/总字数=pc 即为字 c 的频率，所以上式就是每个字的平均信息，而 (2.4) 左端可以变形为：
其中 Nw/总词数=pw 是词 w 的频率，lw 是词 w 的字数，所以 H 是平均每个词的信息量，l 是每个词的平均字数：
因此 L 实际上是按词来记忆时平均每个字的信息量，是我们要比较和优化的终极目标。我们将总的信息量转化为平均到每个字的信息量，是为了得到一个统一的度量标准。
丰富你的词汇量
是不是真如期望一样，分词有助于降低了学习难度？我简单统计了一下，对微信公众号的文章做一个基本的分词后，H≈10.8 比特，每个词平均是 1.5 个字，也就是 l≈1.5，那么 L=7.2 比特，这明显小于逐字记忆的 9.65 比特。这就说明了在中文里边，按词来记忆确实比按字来记忆要轻松。
“分词”这个操作，降低了中文的学习难度，这也是“分词”通常都作为中文 NLP 的第一步的原因。
简单来想，对语言进行分词之后，我们需要记忆的词表变大了，但是每个句子的长度变短了，整体来说学习难度是降低了。所以这也就不难理解为什么要学好英语，就得去背单词，因为丰富我们的词汇量能降低学习语言的难度。
提炼套路
反过来，我们也可以由 L 的最小化，来指导我们无监督地把词库构建出来。这就是“套路是如何炼成的”这门课的重点内容了。
套路之行，始于局部
首先我们将平均字信息熵 L 局部化。所谓局部化，是指考察怎样的两个基本元素合并成一个新的元素后，会导致 L 降低，这样我们就可以逐步合并以完成熵最小化的目标。这里用“基本元素”来描述，是为了将问题一般化，因为字可以合并为词，词可以合并为词组，等等，这个过程是迭代的，迭代过程中“基本元素”是变化的。
“局部化”是接下来大部分内容的基础，其推导过程虽然冗长，但都是比较简单的运算，稍加思考即可弄懂。
假设目前 i 的频数为 Ni，总频数为 N，那么可以估算 Pi=Ni/N，假设 i 的字数为 li，那么就可以算出当前的：
如果将两个相邻的 a,b 合并成一项呢？假设 (a,b) 的频数为 Nab，那么在合并前可以估计 Pab=Nab/N。如果将它们合并为一个“词”来看待，那么总频数实际上是下降了，变为 Ñ =N−Nab，而 Ña=Na−Nab，Ñb=Nb−Nab，其他频数不变，因此我们就可以重新估计各个频率：
于是：
其中：
而：
因此：
我们的目的是让
简明优美的近似
Fab 的表达式过于复杂，以至于难以发现出规律来，我们可以做一些近似。Pab≤Pa,Pb 总是成立的，而很多时候甚至可以认为 Pab≪Pa,Pb，这样一来在使用自然对数时就有：
因为这个近似的条件是要使用自然对数（ln(1+x)≈x），所以我们将下面的 log 全部改为自然对数 ln。代入 Fab 的表达式并去掉 Pab 的二次以上的项，得到：
这个指标就比较简明漂亮了，其中
上面讨论的是两个元素的合并，如果是 k 个基本元素 a=(a1,…,ak) 的合并，那么同样可以推得：
其近似公式为：
推导尽，词库现
现在我们可以看到，要使得目标让
根据 F∗ab 的特点不难看出，F∗ab≫0 的一个必要的条件是
在词库构建这个事情上，还有一个巧妙的招数，那就是对 F∗ab 的“逆运用”：式 F∗ab 告诉我们满足 F∗ab≫0 时，两个元素就应该合并。那么反过来，F∗ab 小于某个 θ 时，是不是就应该切分呢？（逆向思维，从确定哪些要“合并”变为确定哪些要“切分”，所谓“当机立断”）。
这样的话我们只需要用两个元素合并的公式来指导我们对语料进行一个粗糙的切分，然后对切分结果进行统计筛选，就可以得到很多词了。
这样，我们就得到一种简单有效的构建词库的算法：
以前三步得到的词典还是有冗余的，这体现为：直接用这个词典构建一个一元分词模型，那么词典中的有些词永远都不会被分出来，因为那些词可以用它们的子词表示出来，并且子词的概率乘积还大于它本身的概率。
比如在实验中，因为“的、主”以及“主、要”的互信息都大于 1，所以词库中出现了“的主要”这个“词”，但统计发现 p (的主要)< p (的) p (主要)，那么这个词在一元模型分词的时候是不会分出来的，这个“词”放在词库中只会浪费内存，所以要去掉“的主要”这个词，并且把“的主要”的频数加到“的”和“主要”这两个词上面。
因此，根据这个原则，我们可以过滤掉一部分的候选词：
“去冗”这一步的作用还是很明显的，可以去掉 30% 甚至 50% 以上的“不及格”的候选词，以下就是筛选出来的一部分（100 个）：
可以发现，除了“中国人”这个外，其他确实都是我们认识中的“不及格”的词语。
PS：“去冗”这一步需要一些人工规则来对长词进行降权，因为有限的语料对长词的统计是很不充分的，因此长词的概率估计会偏高。而既然是“人工规则”，那就让读者自由发挥了，这里不明确给出。
难道就这么简单？
当然，哪怕是经过上述 4 步，这个算法看起来还是过于简单，以至于会让人怀疑它的效果。有读者应该会想到，
确实有这样的例子，比如在某些语料中，“共和国”中的“和”、“国”，“林心如”中的“心”、“如”，两个字的互信息是比较小的，但三字的互信息就很大了。
然而事实上，落实到中文词库构建这个应用上，这种情况并不多，因为中文跟英文不同，英文基本单位是字母，也就是只有 26 个，它们两两组合才 676 个，甚至三三组合也才一万多个，而汉字本身就有数千个，而理论上汉字对（即 2-gram）就有数百万个了，所以只需要统计 2-gram 就能得到相对充分地反映汉字的组合特征。所以如果出现了这种错例，很大可能是因为这些词不是我们输入语料的显著词，说白了，错了就错了呗。
因此我们基本上不必要讨论三个或三个以上元素合并的公式，用上述的邻字的判别算法即可，在很多情景下它都可以满足我们的需求了。如果要对它进行改进的话，都无法避免引入三阶或更高阶的语言模型，并且还可能需要引入动态规划算法，这会大大降低算法效率。也就是说，改进的思路是有的，但改进的代价会有点大。
识别套路
现在我们可以找出一些自然语言的“套路”——也就是词语了。接下来的问题是，给我们一句话，如何识别出这句话中的套路呢？而对于“词”这个套路，说白了，就是有了词库和词频后如何分词呢？
一元分词新诠释
有了前述讨论，其实就很简单了，自始至终，我们找套路就是为了减轻记忆负担，降低语料总的信息量，而我们有：
也就是最小化总的信息量等价最小化每个句子的信息量。所以对于一个给定的句子，它的最好的分词方案——假设为 w1,w2,…,wn —— 那么应该使得该句子的总信息量：
最小，这其实就是一元分词模型——使得每个词的概率乘积最大，但这里我们通过最小熵原理赋予了它新的诠释。
核心的动态规划
一元分词模型可以通过动态规划来求解。动态规划是 NLP 中的核心算法之一，它是求满足马尔可夫假设的图模型的最优路径的方法。
一般的最优路径是一个复杂度很高的问题，然而由于马尔可夫假设的存在，使得这里存在一个高效的算法，效率为 𝒪(n)，这个算法称之为动态规划，也称为 viterbi 算法，是由安德鲁·维特比（Andrew Viterbi）于 1967 年提出。动态规划的其根本思想是：一条最优路径如果拆分为两部分，那么每一部分都是一条（局部）最优路径。
具体来讲，在最短路径分词中，动态规划就是说：从左往右扫描句子，扫描到当前字时，只保留直到当前字的最优分词结果，以及经过当前字的所有“准最优序列”（防止过早地误切）。
比如，对于句子“中外科学名著”，首先扫描“中”，它就是唯一的分词结果，这个结果被保存下来，经过“中”字的词还有“中外”，因此也要保存下来，也就是说，当扫描到第一个字时，临时变量存的是“中”、“中外”两个候选结果。
第二步，扫描“外”字，这时我们知道“中外”可以有“中 / 外”分成两字，或者直接就“中外”成一个词两种选择，当然，后者概率更大，因此“中 / 外”的结果不保留，只保留“中外”，但是，经过“外”的词还有“外科”，那么应当保留“中 / 外科”的可能性，也就是说，扫描到第二字时，所存的就是“中外”、“中 / 外科”两个候选结果。
接下来到“科”字，由于“中外 / 科”的概率没有“中 / 外科”概率那么大，因此到这一步最优的分词方案是“中 / 外科”，但是经过“科”字的词语还有“科学”，因此此时还有保留“中外 / 科学”的可能性，所以扫描到第三字是，所存的就是“中 / 外科”和“中外 / 科学”。
依此类推，直到最后一字，就可以成功分出“中外 / 科学 / 名著”。整个过程的原则就是：保留至当前字最优的方案，以及不放过经过当前字的所有词（避免过早误切）。
在此，笔者觉得，动态规划在 NLP 中的作用是怎么强调都不为过的，不管你面对的是传统机器学习还是深度学习，都必须掌握动态规划算法，不仅要懂得用，还要懂得自己完整写出来（结合 Trie 树或者 AC 自动机）。
原理再思
尽管我们只是初步完成了无监督构建词库这件事情，但含义远不止于此。
读者不妨头脑风暴一下，我们前面做的是一件非常神奇的事情：我们并不是人为总结一些机械的规则来构建词库，我们是找到了平均字信息熵这个目标，然后试图最小化它，然后就把词库构建出来了。这似乎有点“重演文明”的味道？
做过实验的读者可能又会反驳：你这出来的东西，很多都不是我们认识的“词”呀？
笔者认为，只要让模型具有了演化的能力和方向，那么它究竟演化出什么样子的结果来其实是不重要的。就好比分词，我们并不是为了分词而分词，我们分词是为了后面的任务做准备的，既然如此，何必关心分出来的词准不准的？前面都已经说了，分词的目的是为了降低任务难度罢了。我们真正要关心的，是对最后的任务的处理能力。
听起来有点耍无赖，但事实上这才是真正有人工智能的味道——假如一群真正具有智慧的机器人慢慢地从零开始发展文明，凭什么他发展出来的结果要跟我们的一样呢？
当然，分词只是第一步，事实上出现误差的本质原因是因为我们只关心了分词，而没有做更复杂的语言结构和语义分析。我们后面还会试图做更多的工作，推导更多的“套路”，读者将会慢慢发现，我们最后得到的结果确实是跟语言学现象吻合的。
参考文献
[1]. 无监督句法分析
http://www.52nlp.cn/一种基于生语料的无监督的语法规则学习方法
[2]. “熵”不起：从熵、最大熵原理到最大熵模型（一）
https://kexue.fm/archives/3534
点击以下标题查看作者其他文章：
▲ 戳我查看招聘详情
关于PaperWeekly
PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。
▽ 点击 | 阅读原文 | 进入作者博客